package com.njupt.DynamicProgramming;

import java.util.Arrays;

/**
 * 最长回文子串
 * leetcode 第五题
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * 动态规划
 * 1、确定dp数组的含义
 * 2、寻找状态转移方程，寻找边界体条件
 * 3、dp数组初始化
 * 4、dp数组遍历，从前往后，从后往前。
 */
public class LongestPalindromicSubstring {


    /**
     *
     * 动态规划求最长回文字串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {

        int len = s.length();
        if(len<2){
            return s;
        }

        int maxLen = 1;
        int startIndex = 0;
        //初始化dp数组
        boolean dp[][] = new boolean[len][len];

        //遍历dp数组
        for(int j=1;j<len;j++){
            for (int i = 0; i < j; i++) {
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    if(j-i<3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && (j-i+1)>maxLen){
                    maxLen = j-i+1;
                    startIndex = i;
                }
            }
        }
        return s.substring(startIndex,startIndex+maxLen);
    }

    /**
     * 暴力法
     * @param s
     * @return
     */
    public String longestPalindrome1(String s){

       int len = s.length();
       if(len<2){
           return s;
       }
       int maxLen = 1;
       int startIndex = 0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(isHuiWen(s.substring(i,j+1)) && j-i+1>maxLen){
                    maxLen = j-i+1;
                    startIndex =i;
                }
            }
        }

        return s.substring(startIndex,startIndex+maxLen);
    }

    /**
     * 判断当前字符串是不是回文字符串
     * @param s
     * @return
     */
    public boolean isHuiWen(String s){
        int i = 0;
        int j = s.length()-1;
       while(true){
           if(s.charAt(i)!=s.charAt(j)){
               return false;
           }
           i++;j--;
           if(j<i){
               break;
           }
       }
        return true;
    }


    public static void main(String[] args) {
        new Thread().start();
        String s = "aaaaa";
        LongestPalindromicSubstring test = new LongestPalindromicSubstring();
        //System.out.println(test.isHuiWen("ab"));
        System.out.println(test.longestPalindrome1(s));
    }
}
